#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>

struct node
{
  int data;
  struct node * next;
};

struct stack
{
  struct node * top;
};

void init(struct stack ** src)
{
  (* src) = (struct stack *) malloc(sizeof(struct stack));
  (* src)->top = (struct node *) malloc (sizeof(struct node));
  (* src)->top->data = 0;
  (* src)->top->next = NULL;
}

int pop(struct stack * src)
{
  struct node * des;
  int v;

  printf("src:src->top:%p:%p\n", src, src->top);

  if (src->top->next == NULL)
    printf("the stack is empty.\n");
  else {
    v = src->top->next->data;
	printf("v=%d\n", v);

    des = src->top->next; // 节点指向下一个
	printf("des:src->top->next:%p:%p\n", des, src->top->next);

    src->top = src->top->next; // 栈顶指针下移
	printf("src->top:src->top->next:%p:%p\n", src->top, src->top->next);

    free(des);
    return v;
  }
}

int push(struct stack * src, int value)
{
  struct node * des;

  printf("src:src->top:%p:%p\n", src, src->top);

  des = (struct node *) malloc (sizeof(struct node));
  des->data = value;
  printf("des:des->next:%p:%p\n", des, des->next);

  des->next = src->top->next; // 存储当前栈top->next地址
  printf("des->next:src->top->next:%p:%p\n", des->next, src->top->next);

  src->top->next = des; // 指针指向新节点des. top->next 更新为最新
  printf("src->top:src->top->next:des:%p:%p:%p\n", src->top, src->top->next, des);
}

int gettop(struct stack * src)
{
  int e;

  if (src == NULL)
    printf("the stack is empty.\n");
  e = src->top->next->data;

  return e;
}

void display(struct stack * src)
{
  struct node * des;

  des = src->top->next;
  if (src->top == NULL)
    printf("The stack is empty.\n");
  else {
    printf("The stack :");
    while (des) {
      printf(" %d ", des->data);
      des = des->next;
    }
  }
}

int main()
{
  int n, k, i, select, h, x1, x2;
  struct stack * des;

  printf("Create a empty stack.\n");
  init(&des);

  push(des, 1);
  push(des, 2);
  push(des, 3);
  display(des);

  pop(des);
  display(des);

  pop(des);
  display(des);

  pop(des);
  display(des);



  #if 0
  printf("input a stack length.\n");
  scanf("%d", &n);

  for (i = 1; i <=n; i++) {
    printf("input a stack value:\n");
    scanf("%d", & k);
    push(des, k);
  }

  printf("select 1 : display.\n");
  printf("select 2 : push.\n");
  printf("select 3 : pop.\n");
  printf("select 4 : gettop.\n");
  printf("input a your select (1 - 4) : \n");
  scanf("%d", &select);
	
  switch (select) {
  case 1:
    display(des);
    break;
  case 2:
    printf("input a push a value :\n");
    scanf("%d", &h);
    push(des, h);
    display(des);
    break;
  case 3:
    x1 = pop(des);
    printf("x1->%d\n", x1);
    display(des);
    break;
  case 4:
    x2 = gettop(des);
    printf("x2->%d\n", x2);
    break;
  default:
    break;
  }
  #endif
}
